/**
 * This file contains the signatures for the
 * metaheuristics that are used for solving the
 * clustering problem.
 *
 * @author Carlos Colmentares (06-39380)
 * @author Kelwin Fernandez (07-40888)
 */

#ifndef __CLUSTROPHOBIA__META_HEURISTICS_H_
#define __CLUSTROPHOBIA__META_HEURISTICS_H_

#include <algorithm>
#include "state.h"
#include "clustering_instance.h"
#include "utils.h"

/**
 * This structure will hold the global variables that
 * will be used along the program. There will only be
 * an instance of this structure in the whole program.
 * 
 * @param data_input_file This variable will hold the path
 * to the program's input file with the problem description
 * @param output_file If this file is specified, it should
 * contain the path to a file that the program will write
 * with the problem instance's solution found .
 * @param program_name This variable will only hold the
 * name of program (as it was executed), it is used for
 * error reporting.
 * @param num_clusters This variable will hold the total number
 * of clusters that the solution will contain.
 * @param max_iterations This variable contains the maximum
 * number of iterations that a meta-heuristic is supposed to make
 * before finding a local minimum. However, some metaheuristics
 * may treat it differently.
 * @param meta_heurisitc This variable will contain a string
 * with the shortened name of the metaheuristic to be used.
 * @param criterion This variable will indicate the criterion
 * of quality to be used for evaluating a solution.
 * @param problem_instance This variable will hold an instance
 * of the structure @ref clustering_instance, setted with
 * the data read from the @ref data_input_file.
 * @param num_iterations This variable will hold the number
 * of irerations made by the last metaheuristic. It is used
 * solely for getting statistics.
 */
struct global_data {
    //Data about input/output
    char* data_input_file;
    char* output_file;
    char* program_name;

    //Data about general heuristics
    int num_clusters;
    int max_iterations;
    char* meta_heuristic;
    char* criterion;
    clustering_instance* problem_instance;
    
    //Variables for statistics
    int num_iterations;
    
    // Variables for AntClust Algorithm
    int num_ants;
    double aca_q;
    
    // Variables for Genetic Algorithm
    int population_size;
    int num_couples;
    double mutation_prob;
    double prop_restart;
    int tournament_size;
    
    void initialize();

};

/**
 * This procedure performs the k-means algorithm on the
 * solution that is passed as an argument. If no initial
 * solution is passed, a new one is created. This algorithm
 * succesively move the clusters' centroids to their geometric
 * center.
 * @param initial_state A solution to the problem, which will
 * be refined with the k-means algorithm. If this argument
 * is not passed, then a new random initial solution will be created.
 * @return A solution to the problem after applying the k-means
 * algorithm.
 */
state* k_means(state* initial_state=NULL);

/**
 * The Local Search (LS) metaheuristic is a best-best intensification
 * procedure, it calculates all the neighbors and choses the best
 * of the all. After finding a local minimum or making the maximum
 * numer of iterations, the algorithm stops.
 * @param initial_state A solution to the problem, which will
 * be refined with the local search algorithm. If this argument
 * is not passed, then a new random initial solution will be created.
 * @return A solution to the problem, generated after applying local
 * search on the initial solution.
 */
state* local_search(state* initial_state=NULL);

/**
 * The Iterated Local Search (ILS) metaheuristic is a generalization of
 * the Local Search metaheuristic. It applies iteratively the Local
 * Search procedure over a solution , after finding a local minimum,
 * the solution is "perturbed" for diversifying it. Afterwards the
 * procedure is repeated. The best solution is always stored.
 * @param initial_state A solution to the problem, which will
 * be refined with the taboo search search algorithm. If this argument
 * is not passed, then a new random initial solution will be created.
 * @return A solution to the problem, generated after applying iterated
 * local search on the initial solution.
 */
state* iterated_local_search(state* initial_state=NULL);

/**
 * The Taboo Search (TS) metaheuristic is split in two
 * phases: intensification and diversification. For the intensification
 * it uses a short-time-memory algorithm that remembers the last
 * decisions made for moving through the neighborhood; The objective is
 * to try not to repeat decisions that where already made. For the
 * diversification, a long-time-memory is used; a list of elites
 * is calculated and then the elites are tried to be improved.
 * The solution will be the best of the improved elites.
 * @param initial_state A solution to the problem, which will
 * be refined with the iterated local search algorithm. If this argument
 * is not passed, then a new random initial state will be created.
 * @return A solution to the problem, generated after applying Taboo
 * search on the initial solution.
 */
state* taboo_search(state* initial_state=NULL);

state* variable_neighborhood_search(state* initial_state=NULL);

state* ant_clust_algorithm();

state* ant_clust_hybrid_algorithm();

state* meta_ant_clust_algorithm();

struct individual{
    double** genotype;
    void initialize();
};

state* genetic_algorithm(bool hybrid = false);

state* hybrid_genetic_algorithm();

state* alpha_male_genetic_algorithm();

/**
 * The Simulated Annealing (SA) metaheuristic takes an initial
 * solution and moves randomly in its neighborhood, sometimes
 * accepting neighbors that do not improve the solution.
 * @param initial_state A solution to the problem, which will
 * be refined with the simulated annealing algorithm. If this argument
 * is not passed, then a new random initial state will be created.
 * @return A solution to the problem, generated after applying simulated
 * annealing on the initial solution.
 */
state* simulated_annealing(state* initial_state=NULL);

#endif
